package LimitedTimeGame.Day_0208;

/**
 * @author zxc
 * @date 2023/02/08 08:55
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：删除子文件夹
 * 题目详述 :
 * 你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
 * 如果文件夹folder[i]位于另一个文件夹folder[j]下，那么folder[i]就是folder[j]的 子文件夹 。
 * 文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/'后跟一个或者多个小写英文字母。
 * 例如，"/leetcode"和"/leetcode/problems"都是有效的路径，而空字符串和"/"不是。
 *
 *提示：
 * 1 <= folder.length <= 4 * 104
 * 2 <= folder[i].length <= 100
 * folder[i]只包含小写字母和 '/'
 * folder[i]总是以字符 '/'起始
 * 每个文件夹名都是 唯一 的
 *
 */
public class RemoveSubfolders {
    public static void main(String[] args) {
        System.out.println(removeSubfolders(new String[]{"/a/b/c","/a/b/ca","/a/b/d"}));
    }
    /**
     * 思路 ：
     * 前缀树，来存储所要删除的所有文件路径
     * ===》
     * 1.将folder字符串数组中所有字符串，构建为一颗前缀树;
     * 2.递归遍历前缀树
     * （1）若是遍历到一个字符ch的isWord属性为true的话，则需要去将其加入到result集合数组中国;
     * （2）同时，要注意该字符后面的一个字符s，是否不为"/"，
     *  ===》 若是不为"/"的话，则代表了该文件与之前那个文件是截然不同的文件;
     * （3）若是该字符的后面一个字符s，为"/"的话，就代表了后续文件夹都是当前文件夹的子文件夹;
     *
     * @param folder
     * @return
     */
    public static List<String> removeSubfolders(String[] folder) {
        PrefixTree root = buildPrefixTree(folder);
        List<String> result = new ArrayList<>();
        findMinWord(root , "" , result);
        return result;
    }

    private static void findMinWord(PrefixTree root, String str , List<String> result) {
        if(root.isWord == true){
            result.add(str);
            for (PrefixTree nextChild : root.children) {
                if(nextChild != null && nextChild.value != '/'){
                    findMinWord(nextChild, str + nextChild.value , result);
                }
            }
            return;
        }
        for (PrefixTree child : root.children) {
            if(child != null){
                findMinWord(child , str + child.value , result);
            }
        }
    }

    private static PrefixTree buildPrefixTree(String[] folder) {
        // 根节点
        PrefixTree root = new PrefixTree();
        for (String str : folder) {
            // 临时变量node节点
            PrefixTree node = root;
            // 遍历当前字符串对应的字符数组;
            for (char ch : str.toCharArray()) {
                // ch == '/'的情况 ：
                if(ch == '/'){
                    if(node.children[26] == null){
                        node.children[26] = new PrefixTree();
                        node.children[26].value = '/';
                    }
                    node = node.children[26];
                }
                // ch != '/'的情况 ：
                else {
                    if(node.children[ch - 'a'] == null){
                        node.children[ch - 'a'] = new PrefixTree();
                        node.children[ch - 'a'].value = ch;
                    }
                    node = node.children[ch - 'a'];
                }
//                System.out.println(ch);
            }
//            System.out.println("");
            // 标记某个完整单词的结尾字符为true;
            node.isWord = true;
        }
        return root;
    }

     static class PrefixTree{
        PrefixTree[] children;
        boolean isWord;
        char value;
        PrefixTree(){
            children = new PrefixTree[27];
        }
    }
}
